
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        visited = set()  # 创建存储节点的集合
        # 遍历第一个链表，将所有节点存入集合
        currA = headA
        while currA:
            visited.add(currA)
            currA = currA.next
        # 遍历第二个链表，检查节点是否已在集合中
        currB = headB
        while currB:
            if currB in visited:
                return currB  # 找到相交节点
            currB = currB.next
        return None  # 无相交节点

    def getIntersectionNode2(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        p1 = headA
        p2 = headB
        while p1 != p2:
            p1 = headB if p1 is None else p1.next
            p2 = headA if p2 is None else p2.next
        return p1